//
//  LeetCode55.hpp
//  DataStructuresAndAlgorithms
//
//  Created by blue on 2020/7/24.
//  Copyright © 2020 blue. All rights reserved.
//
/*
 例4-a:跳跃游戏
 
 一个数组存储了非负整型数据，数组中的第i个元素nums[i]，代表了可以从数组第i个位置最多向前跳跃nums[i]步；已知数组各元素的情况下，求是否可以从数组的第0个位置跳跃到数组的最后一个元素的位置？
 
 例如：
 nums = [2,3,1,1,4]，可以从nums[0] = 2 跳跃至 nums[4] = 4;
 nums = [2,3,1,0,4]，不可以从nums[0] = 3 跳跃至 nums[4] = 4。
 
 选自  LeetCode 55 Jump Game
 难度：Medium
 
 ========  ========  ========  ========  ========  ========  ========
 例4-a：思考
 从第i个位置，最远可跳nums[i]步：
 nums = [2,3,1,1,4,...]
 确实最终事发后可以跳至最后一个位置，最困难的地方在于：
 无法直观的观察出从第0个位置开始依次向后的跳跃方式。
 
 例如：
 从第0位置，可以跳跃至第1位置或第2位置；
 从第1位置，可以跳跃至第2、第3、第4位置；
 从第2位置，可以跳跃至第3位置；
 ...
 
 最初在位置0时，应该如何选择，跳至第1位置还是第2位置？
 若选择则跳至了第1位置，之后又该跳跃至第2、第3、第4个位置的哪一个？     思考半分钟！
 
 
 ========  ========  ========  ========  ========  ========  ========
 例4-a：分析
 从第i个位置，最远可跳nums[i]步：
  nums = [2,3,1,1,4,...]
 从第i位置，最远可跳至第index[i]个位置：
 index[i] = i + nums[i];
 index = [2,4,3,4,8,...]
 
 若从第0位置最远可以跳至第i个位置；
 则从第1个位置、第2个位置、...、第i-1个位置。
 
 从第0位置，应该跳至第1、...、第i-1、第i个位置中的哪个？
 应该跳至第1、2、...、i-1、i位置中，又可向前跳至更远位置
 （即index[1]、index[2]、...、index[i-1]、index[i]最大的那个）的位置！ （贪心）
 
 
  ========  ========  ========  ========  ========  ========  ========
 例4-a：贪心规律
 若此时处在第i位置，该位置最远可以跳至第j位置（index[i]），故第i位置还可跳至：
 第i+1、i+2、...、j-1、j位置；
 
 从第i为应跳至第i+1、i+2、...、j-1、j位中可以跳的更远位置的位置，即index[i+1]、index[i+2]、...、index[j-1]、index[j]最大的那个！
 
 原因：假设该位置为x，index[x]最大，故从位置x出发，可以跳至i+1、i+2、...、j-1、j所有位置可以达到的位置；所以跳至位置x最理想。
 
 
 
  ========  ========  ========  ========  ========  ========  ========
 例4-a：算法思路
 1.求从第i位置最远可跳至第index[i]位置；
 根据从第i位置最远可跳nums[i]步：index[i] = nums[i] + i;
 
 2.初始化；
 1）设置变量jump代表当前所处的位置，初始化为0；
 2）设置变量max_index代表从第0位置至第jump位置这个过程中，最远可到达的位置，初始化为index[0]。
 
 3.利用jump扫描index数组，直到jump达到index数组尾部或jump超过max_index，扫描过程中，更新max_index。
 
 4.若最终jump为数组长度，则返回true，否则返回false。
 */
#ifndef LeetCode55_hpp
#define LeetCode55_hpp

#include <stdio.h>
#include <vector>

class Solution55 {
public:
    bool canJump(std::vector<int> &nums);
};

#endif /* LeetCode55_hpp */
